The present invention relates to an improved architecture for content addressable memories and the like and in particular to a range-matching, content addressable memory with an extremely compact architecture.
A common computational task for an electronic computer is that of searching for a particular value in memory. For example, in routing packets over a network, it may be necessary to search for a packet address in memory in order to route the packet through a correct port.
Conventional random access memory operates by receiving an address, designating a memory location and providing access to the data stored at that received address, for example, reading that data or modifying that data. In searching operations, random-access memories typically must access multiple memory addresses in series before a determination may be reached as to whether the data exists in the memory and its location. The time required to complete each sequential memory access can slow the searching operation.
Associative memories (also referred to as content addressable memories) provide a faster way of searching for data. Such memories may receive the value of the data being searched for (a search pattern) and simultaneously review all memory addresses for that pattern. The associative memory typically returns a list of storage addresses holding data that matches the search pattern and these addresses may serve as a link to other needed data. A specialized processor (for example, a network processor) working with an associative memory can perform searches far in excess of the speeds obtainable with conventional random-access memory.
Frequently it is desired to perform a memory search for any value within a particular range of values. This problem may occur, for example, in classifying packets on the Internet or the like where it is desired to know if a packet header falls within a predetermined range of addresses. A straightforward implementation of this problem in a content addressable memory would be to store each value within the range as a separate entry in the content addressable memory; however, this is clearly an inefficient solution.
An alternative approach to searching for ranges can be implemented with ternary content addressable memories (TCAM) which allow for the storage of values of 0, 1, and X (don't care). The placement of X values in the least significant bits in a word stored in the TCAM allows that entry to define a range of different search values so long as the range aligns with a power of two. Defining an arbitrary range can be performed by logical combinations of TCAM but this can quickly become cumbersome and impractical.
Alternatively, it is known to construct range-matching, content addressable memories (RMCAM) in which the associative memory receives entries for upper and lower range ranges for a search, each range providing a numeric value together with a desired arithmetic relationship (for example, EQUAL, GREATER THAN OR EQUAL, LESS THAN OR EQUAL) between a received search pattern and the stored range data. Thus, instead of identifying whether the search pattern equals the value stored in the content addressable memory, the range-matching, content addressable memory identifies whether the search pattern has the desired arithmetic relationship with respect to the range value. A range combining structure of AND gates logically combines outputs from two rows of the range-matching, content addressable memory to provide an output indicating that the received search pattern is within a range defined by the upper and lower range values.
Current range-matching, content addressable memories employ complex memory cell architectures using many transistors for each stored bit. These complex memory cells, when scaled by the large number of required memory cells, can substantially reduce memory densities and increase power consumption of the resulting memory.